package org.gzc.tree;

import java.util.Collections;
import java.util.List;

/**
 * @Description:
 * @Author: guozongchao
 * @Date: 2020/8/13 16:21
 */
public class HuffmanTree {
    //创建结点，待数据和权值
   static class TreeNode implements Comparable<TreeNode>{
        int weight; //权值
        TreeNode left;
        TreeNode right;

        public TreeNode(int weight) {
            this.weight = weight;
        }

        @Override
        public int compareTo(TreeNode o) {
            //从小到大排序
            return this.weight-o.weight;
        }

        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    }

    private static TreeNode createHuffmanTree(List<TreeNode> nodes) {
        while (nodes.size() > 1) {
            //排序 ，从小到大
            Collections.sort(nodes);
            //取出第一棵最小的二叉树
            TreeNode leftNode = nodes.get(0);
            //取出第二棵最小的二叉树
            TreeNode rightNode = nodes.get(1);

            //创建一棵新的二叉树，它的根结点没有 data，只有权值
            TreeNode parent = new TreeNode(leftNode.weight + rightNode.weight);
            parent.left=leftNode;
            parent.right=rightNode;

            //从nodes中删除已经使用过的结点leftNode 和 rightNode
            //将已经创建好的二叉树的根结点放入nodes中
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }


}
